// 组合

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class solution_077 {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int currentNumber = 1;
        DFS(result, n, currentNumber, k, new ArrayList<>());
        return result;
    }

    public void DFS(List<List<Integer>> result, int n, int currentNumber, int k, List<Integer> combination) {
        // 如果数量达到k则停止。
        if (k == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }
        // 数量没达到但是已经到最后一个数，则没有后续组合了
        if (currentNumber > n)
            return;
        // 我们选取每个可能的值进行组合
        for (int i = currentNumber; i <= (n - k + 1); i++) {
            combination.add(i);
            DFS(result, n, i + 1, k - 1, combination);
            combination.remove(combination.size() - 1);
        }
    }
}

public class Solution077 {

}
